Description of the Related Art
The following known literature relating to the above-mentioned technology will be referred to below:
(1) Japanese Patent Kokai Publication No. JP-A-7-121579 PA1 (2) Japanese Patent Kokai Publication No. JP-A-8-329284 PA1 (3) M. S. Mock, "Tetrahedral elements and the Scharfetter-Gummel Method," Proc. NASECODE IV, June, 1985, pp. 36-47 PA1 (4) P. Fleischmann and S. Selberherr, "A New Approach to Fully Understand Unstructured Three-dimensional Delaunay Mesh Generation with Improved Element Quality," Proc. SISPAD, September, 1996, pp. 129-130 PA1 (a) means for excluding from processing and for temporarily storing a specified triangular surface from triangular surfaces that have not yet been subjected to tetrahedral-element extraction processing, and PA1 (b) means which, if a plurality of grid points have become candidate points when a tetrahedral element is extracted using a certain triangular surface, is for partitioning a convex hull domain, which is constituted by the candidate points and the triangular surface, into tetrahedral elements consistently. PA1 (a) first generating a triangular mesh on the surface of an analytic domain; PA1 (b) registering the mesh surfaces of the generated triangular mesh as unprocessed triangular surfaces; and PA1 (c) in order to avoid occurrence of a polyhedral area that cannot be partitioned into tetrahedral elements when one of the unprocessed triangular surfaces is selected and an operation is performed to extract a tetrahedral element having this one triangular surface as a side face thereof, temporarily saving a triangular surface for which a tetrahedral element to be extracted is not uniquely decided, and deferring processing of a triangular surface which may possibly give rise to a polyhedron that cannot be partitioned into tetrahedral elements: PA1 (d) in a case where a plurality of grid points become candidate points when a tetrahedral element is extracting using a certain triangular surface, partitioning a convex hull domain, which comprises the triangular surface and the candidate points, into tetrahedral elements, and, in all other cases, extracting, in the usual manner, a tetrahedral element having the triangular surface as a side face thereof; and PA1 (e) repeating processing from said step (c) in a case where there is an unprocessed triangular surface, and if there is a temporarily saved triangular surface in a case where there is no unprocessed triangular surface, executing processing from said step (c) using said temporarily saved triangular surface as an unprocessed triangular surface. PA1 means for generating a triangular mesh on the surface of an analytic domain, filling in the analytic domain by successively extracting tetrahedral elements having each triangular surface of the triangular mesh as a side face thereof, by using the advancing front method, which gives grid points in advance, as a basic algorithm, and, in order to avoid occurrence of a polyhedral area that cannot be partitioned into tetrahedral elements at this time, using means which temporarily stores triangular surfaces to defer processing of a triangular surface which may possibly give rise to a polyhedron that cannot be partitioned into tetrahedral elements; and PA1 means which, even if a state exists in which six or more grid points lie on a spherical surface that does not internally enclose a grid point, tetrahedralizes the interior of this convex hull domain consistently.
Solving partial differential equations numerically involves generating a discretized mesh which tesselates an analytic domain into minute domains, deriving simultaneous equations which approximate the original partial differential equations and then solving the simultaneous equations. Methods of deriving the simultaneous equations include the finite-element method and the finite-difference method, with the particular method that is used depending upon the nature of the problem to be solved. For example, in the case of a device simulator which computes the electrical characteristic of a semiconductor device through use of a computer, extensive use is made of a method referred to as the control volume method or box integration method derived as a finite-element method. The method defines a minute domain allotted to each discretized grid point and uses a trial function that has a value of 1 within a minute domain and a value of 0 elsewhere.
A method of generating a three-dimensional discretized mesh used in discretized approximation of an equation is set forth in say of Japanese Patent Kokai Publication No. JP-A-7-121579, which deals with the finite-element method. Japanese Patent Kokai Publication No. JP-A-7-121579 proposes a finite-element mesh generation method that includes forming intermediate mesh by partitioning a three-dimensional model to be analyzed into the finite elements of a plurality of tetrahedrons and the finite elements of a pentahedron and/or hexahedron, subdividing each finite element of this intermediate mesh by the finite elements of a hexahedron and forming the entire analytical model as a hexehedral mesh.
When numerical analysis is performed using the control volume method, however, the numerical analysis is rendered unstable if the discretized mesh has not undergone tesselation referred to as Delaunay partitioning. Ordinarily, therefore, it is not possible to apply a mesh generation method for the finite-element method that does not take the nature of such a mesh into account.
Examples of a mesh generation method for a case where a three-dimensional control volume method is used are described in "Tetrahedral elements and the Scharfetter-Gummel Method," Proc. NASECODE IV, pp. 36-47, June 1985 by S. Mock and in the Japanese Patent Kokai Publication No. JP-A-8-329284. These methods involve repeating an operation which includes first creating a Delaunay mesh that includes an analytic domain and then adding a single grid point to this mesh to locally correct the mesh. The correction is carried out in such a manner that the Delaunay-partitioned nature of the mesh will not be lost.
In order to perform the tetrahedral mesh revision by this method, it is necessary to delete mesh elements together with their connecting information and set the connecting information again correctly. Developing a program for executing such processing correctly requires great care and is not easy.
A method of obtaining a Delaunay-partitioned mesh by the advancing front method is disclosed as a method through which the tetrahedral mesh correction operation can be avoided. For example, see "A New Approach to Fully Understand Unstructured Three-dimensional Delaunay Mesh Generation with Improved Element Quality," Proc. SISPAD, pp. 129-130, September, 1996.
An overview of the conventional advancing front method will be described with reference to FIGS. 8 and 9. FIG. 8 is a block diagram illustrating the relationship between processing content and control data in the conventional advancing front method, and FIG. 9 is a flowchart illustrating the processing procedure of the conventional advancing front method.
In the flowchart of FIG. 9, first the surface of an analytic domain is partitioned into a triangular mesh at step S1. Next, at step S2, the mesh surfaces of the triangular mesh created at step S1 are registered as unprocessed triangular surfaces. Step S3 is iterated as long as an unprocessed surface exists. Step S3 includes selecting one unprocessed triangular surface and extracting a tetrahedral element having this triangular surface as one side face thereof. (This step corresponds to means 7 in FIG. 8 for extracting a tetrahedral element having a triangular surface as one side face.)
In order to construct the tetrahedral element, a grid point must be given in addition to the triangular surface. Grid points given inside the analytic domain also are utilized in addition to the grid points of the triangular mesh on the domain surface. The grid points inside the analytic domain can all be given in advance or the grid points can be generated at appropriate positions when the tetrahedral element is extracted.
As the extraction of the tetragonal elements proceeds, the domain that is to be meshed becomes smaller in size. The list of unprocessed triangular surfaces is updated at step S3 of FIG. 9 in such a manner that unprocessed triangular surfaces become a set of triangular surfaces on the periphery of the domain that is to be meshed. In other words, among side faces of a tetrahedral element that has been extracted, surfaces that have been registered in the list of unprocessed surfaces are deleted from the list and triangular surfaces that have been created anew are registered in the list.
FIG. 8 shows the relationship between means provided in a data processing unit 1 and data preserved in a memory device 2 in order to execute the processing described above. This advancing front scheme comprises the processing unit 1, the storage (memory) device 2 and a storage medium 3. The data processing unit 1 includes means 4 for generating a triangular mesh on a surface, initial setting means 5 for setting the surface of a domain on which a mesh is to be generated, and means 7 for extracting a tetrahedron having a triangular surface as one side face thereof. The storage device 2 includes a storage unit 9 for storing a three-dimensional analytic domain, a storage unit 10 for storing a triangular surface mesh, a storage unit 11 for storing an unprocessed triangular surface, and a storage unit 13 for storing a tetrahedral mesh.
In semiconductor simulation, an analytic domain almost always comprises a plurality of areas of different material qualities. This can be dealt with by generating a triangular mesh on the boundary surface between different materials and then applying the processing from step S2 (FIG. 9) onward to each domain of each material.
An overview of an approach for applying the advancing front method to the generation of a Delaunay mesh will be described with reference to FIGS. 10(A)-10(C). For the sake of simplicity, we will discuss the case of a two-dimensional example in which a grid point is not placed inside a domain for which a mesh is to be generated. A property of a Delaunay mesh is that grid points are not enclosed by the circumcircle of a mesh element. The advancing front method is applied as set forth below utilizing this property.
In FIG. 10(A) it is assumed that a grid point exists only a vertex of a polygon of a domain 14a for which a mesh is to be generated. One side 15a on the perimeter of the domain 14 is selected and a grid point (the point at the position of the black circle) that constructs a circle 16a which does not internally contain grid points is found. A triangular element is extracted using (containing) this grid point and the side 15a.
When this is done, the domain 14a to be meshed is updated to a domain 14b, then one side 15b on the perimeter thereof is selected and a triangular element is extracted in similar fashion, as shown in FIG. 10(b). This is iterated until the domain 14c for which a mesh is to be generated vanishes, as illustrated in FIG. 10(C) (i.e., the domain 14c now becomes a triangular element with a selected side 15c and a circle 16c).
Problems Encountered in the Art
In the course of investigation toward the present invention the followings problems have been encountered.
In the case of three dimensions, a grid point that constructs a circumsphere which does not internally contain grid points is found on the triangular surface of the outer periphery of the domain for which the mesh is to be generated.
Processing can be executed in a similar manner also in a case where a grid point is placed within an analytic domain beforehand. In a case where a grid point is generated when a tetrahedral element is extracted, care must be taken so as not to position the grid point within a circumcircle or circumsphere of a mesh element that has already been generated. However, such processing is not impossible. Nevertheless, in a case where decision processing is to be included or any position whatsoever falls within a circumcircle or circumsphere, this is not an appropriate method of computation when one considers that control is performed so as not to become trapped in an endless loop in an effort to generate points. In other words, if the advancing front method is to be used, then grid points should be given in advance.
Thus, a problem which arises in a case where the advancing front method is utilized in generation of a three-dimensional tetrahedral mesh is that a state in which tetrahedral elements cannot be extracted can occur.
FIG. 3 illustrates a triangular prism domain that has not been partitioned into tetrahedral elements, the domain being bounded entirely by triangular surfaces. In this case, intersection of grid sides occurs regardless of how the tetrahedron is extracted. This condition is capable of occurring in a case where six or more points are located on the same spherical surface and, moreover, four or more points are located on the same plane, as in the domain of a triangular prism or domain of a rectangular prism.
If five or more points are located on a surface of sphere that does not internally contain grid points in a case where the control volume method is used, it is unnecessary to generate the side of a grid that passes through the interior of the convex hull of these grid points, and the convex hull can be treated as one element. If this is done, however, a polyhedral element having an arbitrary number of sides will be generated. This will necessitate a characteristic analyzer and an analytical result display unit which can manage these elements. This is extremely inconvenient. Since it is possible in principle to perform tetrahedralization without causing the intersection of the sides of grids, finding how to perform such partitioning is appropriate.